/* 排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定	是否原地排序
冒泡排序（Bubble Sort）	O(n²)	O(n²)	O(1)	✅ 是	✅ 是
选择排序（Selection Sort）	O(n²)	O(n²)	O(1)	❌ 否	✅ 是
插入排序（Insertion Sort）	O(n²)	O(n²)	O(1)	✅ 是	✅ 是
希尔排序（Shell Sort）	O(n^1.3) ~ O(n^1.5)	O(n²)	O(1)	❌ 否	✅ 是
归并排序（Merge Sort）	O(n log n)	O(n log n)	O(n)	✅ 是	❌ 否
快速排序（Quick Sort）	O(n log n)	O(n²)	O(log n)	❌ 否	✅ 是
堆排序（Heap Sort）	O(n log n)	O(n log n)	O(1)	❌ 否	✅ 是
计数排序（Counting Sort）	O(n + k)	O(n + k)	O(k)	✅ 是	❌ 否
桶排序（Bucket Sort）	O(n + k)	O(n²)	O(n + k)	✅ 是	❌ 否
基数排序（Radix Sort）	O(nk)	O(nk)	O(n + k)	✅ 是	❌ 否 */



//一.冒泡排序
/* 两两比较相邻元素，发现逆序就交换；

最坏是 O(n²)，简单但效率低。 */
//不是这样冒泡的，下面这个是选择排序，一定是n2
/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
let result = null
function BubbleSort(arr){
    for(let i=0;i<arr.length-1;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[i]>arr[j]){
                [arr[i],arr[j]] = [arr[j],arr[i]]
            }
        }
    }
    return arr
}
console.log(BubbleSort(arr)); */

//下面才是冒泡的正确手段
//是相邻的两两交换
/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function BubbleSort(arr){
    let result 
    for(let i=0;i<arr.length-1;i++){
        result = false
        for(let j=0;j<arr.length-1-i;j++){
            if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
                result = true
            }
            
        }
        if (!result) break;
    }
    return arr 
}
console.log(BubbleSort(arr));  */

//优化手段
//在i循环里面设置一个值为false
//在j循环里面设置这个值改为true
//如果j循环结束都没有变为true，则判定结束






//二.快速排序
/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function quickSort(arr){
if (arr.length<=1) return arr;
     let inital = arr[0]
     let left =[]
     let right=[]
     for(let i=1;i<arr.length;i++){
        if(arr[i]>inital){
        right.push(arr[i])
   } else{
        left.push(arr[i]) 
}
    return [...quickSort(left),inital,...quickSort(right)]
}
}
console.log(quickSort(arr)); */
/* 选一个“基准”值，左边放比它小的，右边放大的，然后递归；

平均 O(n log n)，但最坏会退化成 O(n²)，通常加个随机基准避免退化。 */
//1.创建数组版
/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function quickSort(arr){
    if (arr.length <= 1) return arr; // 递归出口
let standard = arr[0]
let left = []
let right =[]
for(let i = 1;i<arr.length;i++){
    if(arr[i]>standard){
        right.push(arr[i])
    }
    else{
        left.push(arr[i])
    }
}

return [...quickSort(left),standard,...quickSort(right)]        //将每次递归结果以数组的形式返回，知道递归完成，返回最后值
}
console.log(quickSort(arr)); */


//2.不创建数组版....




//三.选择排序      每次遍历完成后都可以将正确的值放在对的位置

/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function selectionSort(arr){
    for(let i=0;i<arr.length-1;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[j]<arr[i]){
                [arr[i],arr[j]] = [arr[j],arr[i]]
            }
        }
    }
    return arr
}
console.log(selectionSort(arr)); */





// 四.归并排序   

/* 递归拆分数组，然后合并时排序；

时间复杂度稳定 O(n log n)，但需要额外空间，适合处理大数据或链表排序。 */

/* var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function mergeSort(arr){
    if (arr.length===1) return arr
    let middle = Math.floor(arr.length/2)
    let left = mergeSort(arr.slice(0,middle))
    let right = mergeSort(arr.slice(middle))
    return a(left,right)
}

function a(left,right){
    let i = 0
    let j = 0
    const newArr = []
    while(left.length>i&&right.length>j){
        if(left[i]>right[j]){
            newArr.push(right[j])
            j++
        }else{
            newArr.push(left[i])
            i++
    }
    }
    return newArr.concat(left.slice(i)).concat(right.slice(j))
}
console.log(mergeSort(arr));
 */


//归并排序
var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
function mergeSort(arr){
    let middle = Math.floor(arr.length/2)
    let left = [];
    let right = [];
    
}